/**
 * Test algorithms for JettHoughts
 * 
 * Created 12/02/2012
 * 
 * @author Vasili Svirski
 * @version 0.01
 */

package com.jetthoughts.algorithms;

/**
 * Permutation algorithm
 *
 */
public class Permutation {

	// print N! permutation of the characters of the string s (in order)
	public  static void permOrder(String s) {
		permOrder("", s); 
	}

	private static void permOrder(String prefix, String s) {
		int N = s.length();

		if (N == 0) System.out.println(prefix);
		else {
			for (int i = 0; i < N; i++)
				permOrder(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
		}
	}

	// print N! permutation of the elements of array a (not in order)
	public static void permNOrder(String s) {
		int N = s.length();
		char[] a = new char[N];
		for (int i = 0; i < N; i++)
			a[i] = s.charAt(i);
		permNOrder(a, N);
	}

	private static void permNOrder(char[] a, int n) {
		if (n == 1) {
			System.out.println(a);
			return;
		}

		for (int i = 0; i < n; i++) {
			swap(a, i, n-1);
			permNOrder(a, n-1);
			swap(a, i, n-1);
		}
	}  

	// swap the characters at indices i and j
	private static void swap(char[] a, int i, int j) {
		char c;
		c = a[i]; 
		a[i] = a[j]; 
		a[j] = c;
	}

	/**
	 * Run permutations
	 * @param args
	 */
	public static void main(String[] args) {
		String elements = "123";
		permOrder(elements);
		System.out.println();
		permNOrder(elements);
	}
}